package problem146_LRU_Cache;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
	private int capacity;
	private Map<Integer,Node> map;
	private Node head;
	private Node tail;
    
    public LRUCache(int capacity) {
        this.capacity=capacity;
        map=new HashMap<>();
    }
    
    private void setHead(Node node){
    	node.next=head;
    	node.pre=null;
    	if(head!=null)
    		head.pre=node;
    	head=node;
    	if(tail==null)
    		tail=head;
    }
    
    private void remove(Node node){
    	if(node.pre!=null){
    		node.pre.next=node.next;
    	}else{
    		head=node.next;
    	}
    	if(node.next!=null){
    		node.next.pre=node.pre;
    	}else{
    		tail=node.pre;
    	}
    }
    
    public int get(int key) {
    	if(map.containsKey(key)){
    		Node n=map.get(key);
    		remove(n);
    		setHead(n);
    		return n.value;
    	}
		return -1;
    }
    
    public void set(int key, int value) {
       if(map.containsKey(key)){
    	   Node node=map.get(key);
    	   node.value=value;
    	   remove(node);
    	   setHead(node);
       }else{
    	   Node newNode=new Node(key,value);
    	   if(map.size()>=capacity){
    		   map.remove(tail.key);
    		   remove(tail);
    	   }
    	   setHead(newNode);
    	   map.put(key, newNode);
       }
    }
    
    private class Node{
    	int key;
    	int value;
    	Node pre;
    	Node next;
    	
		public Node(int key,int value) {
			super();
			this.key=key;
			this.value = value;
		}
    }
}